package leetcode.alg.demo;

/**
 * 给你一个 山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小 的下标 index 值。
 *
 * 如果不存在这样的下标 index，就请返回 -1。
 *
 *  
 *
 * 何为山脉数组？如果数组 A 是一个山脉数组的话，那它满足如下条件：
 *
 * 首先，A.length >= 3
 *
 * 其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
 *
 * A[0] < A[1] < ... A[i-1] < A[i]
 * A[i] > A[i+1] > ... > A[A.length - 1]
 *  
 *
 * 你将 不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
 *
 * MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
 * MountainArray.length() - 会返回该数组的长度
 *
 * 示例 1：
 *
 * 输入：array = [1,2,3,4,5,3,1], target = 3
 * 输出：2
 * 解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
 *
 * 示例 2：
 *
 * 输入：array = [0,1,2,4,2,1], target = 3
 * 输出：-1
 * 解释：3 在数组中没有出现，返回 -1。
 *
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-in-mountain-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Found_target_in_mountain_array {
    public static void main(String[] args){
        int[] arrays = {1,2,3,4,5,3,1};
        MountainArray mountainArray = new MountainArray(arrays);
        System.out.println(findInMountainArray(3, mountainArray));
    }

    public static int findInMountainArray(int target, MountainArray mountainArr) {
        int middle_index = findMaxValueIndex(mountainArr);
        int start_index = 0;
        int end_index = mountainArr.length() - 1;
        int left_index =  findTargetIndex(mountainArr, target, start_index, middle_index, true);
        int right_index = findTargetIndex(mountainArr, target, middle_index, end_index, false);
        if(left_index != -1){
            return left_index;
        }else{
            return right_index;
        }
    }

    public static int findTargetIndex(MountainArray mountainArr, int target, int start_index, int end_index, boolean flag){
        int middle_index = (start_index + end_index) / 2;
        while (start_index + 1 < end_index){
            if(mountainArr.get(middle_index) < target){
                if(flag){
                    start_index = middle_index;
                }else{
                    end_index = middle_index;
                }
            }else{
                if(flag){
                    end_index = middle_index;
                }else{
                    start_index = middle_index;
                }
            }
            middle_index = (start_index + end_index) / 2;
        }
        if(mountainArr.get(start_index) == target){
            return start_index;
        }else if(mountainArr.get(end_index) == target){
            return end_index;
        }
        return -1;
    }

    public static int findMaxValueIndex(MountainArray mountainArr){
        int start_index = 0;
        int end_index = mountainArr.length() - 1;
        int middle_index = (end_index + start_index) / 2;
        while (start_index < middle_index){
            if(mountainArr.get(middle_index - 1) < mountainArr.get(middle_index)){
                start_index = middle_index;
            }else {
                end_index = middle_index;
            }
            middle_index = (end_index + start_index) / 2;
        }
        return middle_index;
    }

    static class MountainArray{
        int[] target_array;
        public MountainArray(int[] sources_array){
            target_array = sources_array;
        }

        public int get(int index) {
            return target_array[index];
        }

        public int length() {
            return target_array.length;
        }
    }
}